Search Engines笔记 - Query Processing

CMU 11642 的课程笔记。搜索引擎是怎么处理 query 的？三种方法，Term-at-a-time(TAAT)，Document-at-a-time(DAAT)，TAAT/DAAT hybrids。

TAAT

主要思路：

• 处理完一个 inverted list 再处理下一个。
• 每处理完一个 inverted list，部分更新 document score。

优点：

• 易于理解
• 高效

缺点：

• 难以控制内存
  每个 operator 都会同时在内存里存 3 个 list(arg1,arg2,result)
  每个深度为 d 的 query 都会同时在内存里存 d+2 个 list。
• 可能会 run out of memory
  包含有 frequent term 的 query (很长的 inverted list)
  复杂的 query (更多的 inverted list)
  同时处理多个 query 的系统

所以 TAAT 很少用在 large-scale systems。

Eg.#AND(a b #OR (c #NEAR/3(d e)) f)
转化成 query tree

          AND
(a   b     OR            f)
         (c  NEAR/3
              (d  e))

Retrieve a
Retrieve b
a AND b -> Result(AND_1)
Retrieve c
Retrieve d
Retrieve e
d NEAR/3 e -> Result(NEAR)
c OR Result(NEAR) -> Result(OR)
Result(AND_1) AND Result(OR) -> Result(AND_2)
Retrieve f
Result(AND_2) AND f -> Result(Q)

Memory usage
内存中同时存在 5 个 list

size(a AND b) +
size(c) +
size(d) + size(e) + size(d NEAR/3 e) bytes

DAAT

主要思路：

• 处理完一篇文档后，再处理下一篇文档。
• 每处理一篇文档，就算出 complete score

找到所有 term 的 inverted list，每个 inverted list 分配一个 iterator，分配一个空的 result list。之后找到每个 inverted list 当前的 doc id，取最小的 doc id，算出当前分数，保存到 result list 中，然后把这个 iterator 往下移一个 doc id，重复这个过程。

简化一下，主要就重复两件事：

• update the score
• advance the pointer

代码描述

q.initialize()
while (q.hasNext())
  q.evalNext() returns next [docid,score] tuple

优点：

• 易于进行内存管理
  需要同时 access 所有 args 的 inverted list (seems bad)，然而，这些 inverted list 可以以 block 的形式分批从 disk 读进 RAM。等当前 block 处理完了再读下一个 block，这样处理一个 query 所需的内存就取决于 block 的大小。
• 可以进行很多 query evaluation 的优化
  低分文档只进行 partial evaluation

所以 TAAT 经常用在 large-scale systems。

TAAT/DAAT hybrids

平衡 Efficiency 和 memory control。Eg. block-based TAAT(compute TAAT over blocks of document ids)